#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/11 22:59
# @USER    : Shengji He
# @File    : FirstMissingPositive.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        """
        Given an unsorted integer array, find the smallest missing positive integer.

        Example 1:
            Input: [1,2,0]

            Output: 3
        Example 2:
            Input: [3,4,-1,1]

            Output: 2
        Example 3:
            Input: [7,8,9,11,12]

            Output: 1

        Note:
            - Your algorithm should run in O(n) time and uses constant extra space.

        :param nums: List[int]
        :return: int
        """
        if not nums:
            return 1
        for i in range(len(nums)):
            while 0 < nums[i] <= len(nums) and nums[i] != nums[nums[i] - 1]:
                 nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i in range(len(nums)):
            if nums[i] != i + 1:
                return i + 1
        return len(nums) + 1
        #
        # for i in range(1, 2 ** 31):
        #     if i not in nums:
        #         return i


if __name__ == '__main__':
    nums = [1]
    # nums = [7,8,9,11,12]
    # nums = [1,2,0]
    # nums = [3,4,-1,1]
    S = Solution()
    print(S.firstMissingPositive(nums))
    print('done')
